dofile("Tile.lua")

openlist = {}
openlist.n = 0
closedlist = {}
closedlist.n = 0
local path={}
path.n = 0

-- Declaracao da classe (tabela) Agent 
Map = {
	tileMap = {},
	tilesize = 32,
	windowWidth = 320,
	windowHeight = 320,
	tileTextures = {},
	tile_images = {}
}

function Map:new(o)
	o = o or {}
	setmetatable(o, self)
    self.__index = self
    return o	
end
	
	-- Metodos
function Map:get_x_y_line_column(index)
	local n_tiles = (self.windowWidth / self.tilesize)
	local l = math.floor(index/ n_tiles)
	local c = math.mod(index, n_tiles)
	local x = (c * self.tilesize) + (self.tilesize/2)
	local y = (l * self.tilesize) + (self.tilesize/2)
	return x, y, l, c 
end

function Map:get_index(x, y)
	local n_tiles = (self.windowWidth / self.tilesize)
	local c = math.floor(x / self.tilesize)
	local l = math.floor(y / self.tilesize)
	local index = c + l * n_tiles
	return index
end
	
function Map:generateSuccessors(index)
	local Tsuccessors = {}
	Tsuccessors.n = 0
	local n_tiles = (self.windowWidth / self.tilesize)
	local index_x, index_y, index_l, index_c = self:get_x_y_line_column(index)	
	-- EAST
	index_x, index_y,  adjt_l, adjt_c = self:get_x_y_line_column(index + 1)	
	if ((index_l == adjt_l) or (index_c == adjt_c)) and
	   (self.tileMap[index + 1] and self.tileMap[index + 1]:get_obstruction() == 0) then
		Tsuccessors.n = Tsuccessors.n + 1
		Tsuccessors[Tsuccessors.n] = index + 1
	end
	-- NORTH
	index_x, index_y, adjt_l, adjt_c = self:get_x_y_line_column(index + n_tiles)
	if ((index_l == adjt_l) or (index_c == adjt_c)) and
	   (self.tileMap[index + n_tiles] and self.tileMap[index + n_tiles]:get_obstruction() == 0) then
		Tsuccessors.n = Tsuccessors.n + 1
		Tsuccessors[Tsuccessors.n] = index + n_tiles
	end	
	-- WEST
	index_x, index_y, adjt_l, adjt_c = self:get_x_y_line_column(index - 1)
	if ((index_l == adjt_l) or (index_c == adjt_c)) and
	   (self.tileMap[index-1] and self.tileMap[index-1]:get_obstruction() == 0) then
		Tsuccessors.n = Tsuccessors.n + 1
		Tsuccessors[Tsuccessors.n] = index - 1
	end
	-- SOUTH
	index_x, index_y, adjt_l, adjt_c = self:get_x_y_line_column(index - n_tiles)
	if ((index_l == adjt_l) or (index_c == adjt_c)) and
	   (self.tileMap[index - n_tiles] and self.tileMap[index - n_tiles]:get_obstruction() == 0) then
		Tsuccessors.n = Tsuccessors.n + 1
		Tsuccessors[Tsuccessors.n] = index - n_tiles
	end		
--	-- NORTHEAST
--	index_x, index_y, adjt_l, adjt_c = self:get_x_y_line_column(index + n_tiles)
--	if ((index_l == adjt_l) or (index_c == adjt_c)) and
--	   (self.tileMap[index + n_tiles + 1] and self.tileMap[index + n_tiles + 1]:get_obstruction() == 0) then
--		Tsuccessors.n = Tsuccessors.n + 1
--		Tsuccessors[Tsuccessors.n] = index + n_tiles + 1
--	end
--	-- NORTHWEST
--	index_x, index_y, adjt_l, adjt_c = self:get_x_y_line_column(index + n_tiles)
--	if ((index_l == adjt_l) or (index_c == adjt_c)) and
--	   (self.tileMap[index + n_tiles - 1] and self.tileMap[index + n_tiles - 1]:get_obstruction() == 0) then
--		Tsuccessors.n = Tsuccessors.n + 1
--		Tsuccessors[Tsuccessors.n] = index + n_tiles - 1
--	end
--	-- SOUTHEAST
--	index_x, index_y, adjt_l, adjt_c = self:get_x_y_line_column(index + n_tiles)
--	if ((index_l == adjt_l) or (index_c == adjt_c)) and
--	   (self.tileMap[index - n_tiles + 1] and self.tileMap[index - n_tiles + 1]:get_obstruction() == 0) then
--		Tsuccessors.n = Tsuccessors.n + 1
--		Tsuccessors[Tsuccessors.n] = index - n_tiles + 1
--	end
--	-- SOUTHWEST
--	index_x, index_y, adjt_l, adjt_c = self:get_x_y_line_column(index + n_tiles)
--	if ((index_l == adjt_l) or (index_c == adjt_c)) and
--	   (self.tileMap[index - n_tiles - 1] and self.tileMap[index - n_tiles - 1]:get_obstruction() == 0) then
--		Tsuccessors.n = Tsuccessors.n + 1
--		Tsuccessors[Tsuccessors.n] = index - n_tiles - 1
--	end
	return Tsuccessors	
end

function Map:findLowestF()
	local i = 1
	local lowest_f = 100000000
	local lowest_f_index = -1
	local g = 0
	while (i <= openlist.n) do
		local f = openlist[i].f
		if (f <= lowest_f) then
			lowest_f = f
			lowest_f_index = openlist[i].index
			g = openlist[i].g
		end  
		i = i + 1
	end	
	return lowest_f_index, g	
end
	
function Map:addToClosedlist(index, x, y, g, h)
	closedlist.n = closedlist.n + 1
	closedlist[closedlist.n] = {}
	closedlist[closedlist.n].index = index
	closedlist[closedlist.n].x = x
	closedlist[closedlist.n].y = y
	closedlist[closedlist.n].g = g
	closedlist[closedlist.n].h = h
	closedlist[closedlist.n].f = g + h
end

function Map:addToOpenlist(index, x, y, g, h)
	openlist.n = openlist.n + 1
	openlist[openlist.n] = {}
	openlist[openlist.n].index = index
	openlist[openlist.n].x = x
	openlist[openlist.n].y = y	
	openlist[openlist.n].g = g
	openlist[openlist.n].h = h
	openlist[openlist.n].f = g + h	
end
	
function Map:removeFromClosedlist(index)
	local i = 1
	while(i <= closedlist.n) do
		if(closedlist[i].index == index) then
			closedlist.n = closedlist.n - 1
			break
		end		
		i = i + 1
	end
	
	while(i <= closedlist.n) do
		closedlist[i] = closedlist[i + 1]
		i = i + 1
	end
end
	
function Map:findInClosedlist(index)
	local i = 1
	while(i <= closedlist.n) do
		if (closedlist[i].index == index) then
			return i
		end
		i = i + 1
	end
	return 0	
end
	
function Map:findInOpenlist(index)
	local i = 1
	while(i <= openlist.n) do
		if (openlist[i].index == index) then
			return i
		end
		i = i + 1
	end
	return 0	
end
	
function Map:removeFromOpenlist(index)
	local i = 1
	while(i <= openlist.n) do
		if  (openlist[i].index == index) then
			openlist.n = openlist.n - 1
			break
		end	
		i = i + 1		
	end	
	while(i <= openlist.n) do
		openlist[i] = openlist[i + 1]
		i = i + 1
	end		
end
	
function Map:generateH(current_x, current_y, node_goal_x, node_goal_y)
	local h = math.sqrt(	(node_goal_x - current_x) * (node_goal_x - current_x) +
							(node_goal_y - current_y) * (node_goal_y - current_y) )
	return h 
end
	
function Map:getCost(node1x, node1y, node2x, node2y)
	local h = math.sqrt(	(node2x - node1x) * (node2x - node1x) +
							(node2y - node1y) * (node2y - node1y) )
	return h
end
	
function Map:get_tile(x, y)
	local index = self:get_index(x, y)
	return self.tileMap[index]
end 
	
function Map:get_tilesize()
	return self.tilesize
end
	
function Map:render(canvas)
	local j = 0
	local n_tiles = (self.windowHeight / self.tilesize)
	while (j < n_tiles) do
		local i = 0
		while (i < n_tiles) do
			local tileset = math.floor(self.tileMap[i + (j * n_tiles)]:get_index() /200)
			local index = self.tileMap[i + (j * n_tiles)]:get_index() - (tileset*200)				
			local x1 = 0
			local y1 = 0
			x1 = i * self.tilesize
			y1 = j * self.tilesize				
			
			local imgl = nil
			local imgc = nil
			if tileset < 50  then
				imgl = math.floor(index/8)
				imgc = math.mod(index, 8)
			else
				imgl = math.floor(index/3)
				imgc = math.mod(index, 3)
			end
			local imgx1 = imgc * self.tilesize
			local imgx2 = imgx1 + self.tilesize
			local imgy1 = imgl * self.tilesize
			local imgy2 = imgy1 + self.tilesize
			local image = self.tile_images[tileset]
			
			cd.Activate(canvas)
			image:cdCanvasPutImageRect(canvas, x1, y1, self.tilesize, self.tilesize, imgx1, imgx2, imgy1, imgy2)
			i = i + 1
		end
		j = j + 1
	end					
end	
	
function Map:printPath(node_start_x, node_start_y, node_goal_x, node_goal_y)
	local goal_index = self:get_index(node_goal_x, node_goal_y)
	local start_index = self:get_index(node_start_x, node_start_y)
	local index = goal_index 
	io.write("PATH:")
	while(index ~= start_index) do
		io.write(index.." ")
		--renderChar(path[index].x, path[index].y, cd.CYAN)		
		index = path[index].parent
	end
	io.write("\n")
	--renderChar(node_start_x + 5, node_start_y + 5, cd.CYAN)	
end
	
function Map:pathFind(node_start_x, node_start_y, node_goal_x, node_goal_y)
	--define goal node
	node_goal = self:get_index(node_goal_x, node_goal_y)
	--define start node
	node_start = self:get_index(node_start_x, node_start_y)
	--insert goal node into the openlist
	self:addToOpenlist(node_start, node_start_x, node_start_y, 0, self:generateH(node_start_x, node_start_y, node_goal_x, node_goal_y))
	while(openlist.n > 0) do
		-- get lowest f node off the openlist
		local node_n, n_g = self:findLowestF()
		local node_n_x, node_n_y, l, c = self:get_x_y_line_column(node_n)
		--renderChar(node_n_x, node_n_y, cd.WHITE)
		self:removeFromOpenlist(node_n)
		-- add it to the closed list
		self:addToClosedlist(node_n, node_n_x, node_n_y, n_g, self:generateH(node_n_x, node_n_y, node_goal_x, node_goal_y))
		-- if n is the same as node_goal we have found the solution
		if (node_n == node_goal) then
			--print("LoL!!!")
			openlist = {}
			closedlist = {}
			openlist.n = 0
			closedlist.n = 0				
			-- contando elementos
			local i = 0
			local rt = {}
			local index = node_goal
			while(index ~= node_start) do
				i = i + 1
				rt[i] = {}
				rt[i].index = index
				rt[i].x = path[index].x
				rt[i].y = path[index].y
				rt[i].parent = path[index].parent					
				index = path[index].parent
			end		
			-- invertendo o vetor de path
			rt.n = i
			while(i > 0) do
				local j = 1
				local temp = {}
				local acabou = 1
				while(j < i) do
					temp = rt[j]
					rt[j] = rt[j + 1]
					rt[j + 1] = temp
					j = j + 1
					acabou = 0
				end
				if acabou == 1 then
					break
				end
				i = i - 1			
			end				
			return rt
		--otherwise
		else
			--Generate each successor node n' of n
			local Tsuccessors = self:generateSuccessors(node_n)
			local i = 1
			--for each successor node n' of n
			while(i <= Tsuccessors.n) do				
				--Set h(n') to be the heuristically estimate distance to node_goal
				--Set g(n') to be g(n) plus the cost to get to n' from n
				--Set f(n') to be g(n') plus h(n')
				local successor_x, successor_y, l, c = self:get_x_y_line_column(Tsuccessors[i]) 					
				local successor_h = self:generateH(successor_x, successor_y, node_goal_x, node_goal_y)
				local successor_g = n_g + self:getCost(node_n_x, node_n_y, successor_x, successor_y) 
				local successor_f = successor_g + successor_h
				
				--if n' is on the OPEN list and the existing one is as good or better then discard n' and continue
				local openlist_index = self:findInOpenlist(Tsuccessors[i])
				local closedlist_index = self:findInClosedlist(Tsuccessors[i])
				if (	openlist_index ~= 0 and
					successor_f >= openlist[openlist_index].f  ) then
						-- do nothing										
												
				--if n' is on the CLOSED list and the existing one is as good or better then discard n' and continue
				elseif (closedlist_index ~= 0 and
					successor_f >= closedlist[closedlist_index].f ) then
						-- do nothing
				else
					--Set the parent of n' to n 
					--???
					path[Tsuccessors[i]] = {}
					path[Tsuccessors[i]].x = successor_x
					path[Tsuccessors[i]].y = successor_y
					path[Tsuccessors[i]].parent = node_n				
					
					--Remove occurrences with lower or equal value of n' from OPEN and CLOSED
					self:removeFromOpenlist(Tsuccessors[i])
					self:removeFromClosedlist(Tsuccessors[i])
					--Add n' with new f value to the OPEN list
					self:addToOpenlist(Tsuccessors[i], successor_x, successor_y, successor_g, successor_h)					
				end
				i = i + 1
			end						
		end
	end
	--print("Nao existe caminho possivel.")
	openlist = {}
	closedlist = {}
	openlist.n = 0
	closedlist.n = 0	
	
	return nil		
end
	
function Map:loadImages()
	io.write("Loading tileset images...\t")
	-- Loading tilesets
	local ifile = io.open("tilesets/tileset.lst", "r")		
	local ifile2 = nil
	local tileset = ifile:read("*l")
	local i = 0
	while(tileset ~= nil) do
		--image_buffer = cd.CreateBitmap(800, 600, cd.RGB);
		ifile2 = im.FileOpen("tilesets/"..tileset..".png")
		self.tile_images[i] = ifile2:LoadBitmap()
		ifile2:Close()
		i = i + 1
		tileset = ifile:read("*l")		
	end
	ifile:close()
	io.write("[OK]\n")
	io.write("Loading autotile images...\t")
	-- Loading autotiles
	ifile = io.open("autotiles/autotile.lst", "r")		
	tileset = ifile:read("*l")
	while(tileset ~= nil) do
		ifile2 = im.FileOpen("autotiles/"..tileset..".png")
		self.tile_images[i] = ifile2:LoadBitmap()
		ifile2:Close()
		i = i + 1		
		tileset = ifile:read("*l")
	end
	ifile:close()	
	io.write("[OK]\n")
end
	
function Map:loadMapFile(mapfile)
	local ifile, error = io.open(mapfile)
	local width = ifile:read("*n")
	local height = ifile:read("*n")
	
	local l = height - 1
	local c = 0
	
	while(l >= 0) do
       	while(c < width) do
               	local index = ifile:read("*n")
               	local i = c + (l * width)
               	self.tileMap[i] = Tile:new()
       				self.tileMap[i]:set_index(index)
       				self.tileMap[i]:set_obstruction(0)
               	c = c + 1
               	i = i + 1
       	end
       	c = 0
       	l = l - 1       	
	end		
	ifile:close()
end
